package 图.最短路径;


import 抽象数据类型.Bag;
import 抽象数据类型.DirectedEdge;
import 抽象数据类型.EdgeWeightedGraph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-14
 */
public class 有向加权拓扑排序 {
    public static void main(String[] args) {
        int[] arr1 = {0, 1, 0, 1, 1, 4, 2, 1};
        int[] arr2 = {1, 2, 2, 4, 3, 3, 3, 3};
        double[] weight = {1, 2, 3, 2, 3, 3, 2, 3};
        EdgeWeightedGraph G = new EdgeWeightedGraph(5);
        G.addGraph(arr1, arr2, weight);
        TopologicalBFS top = new TopologicalBFS(G);
        for (Integer w : top.order()) {
            System.out.println(w);
        }

    }

    static class TopologicalBFS {
        Queue<Integer> order;

        public TopologicalBFS(EdgeWeightedGraph G) {
            Degrees degrees = new Degrees(G);
            EdgeWeightedGraph g = degrees.g;
            Queue<Integer> queue = new LinkedList();
            order = new LinkedList<>();
            for (Integer source : degrees.sources()) {
                queue.offer(source);
            }
            while (!queue.isEmpty()) {
                Integer w = queue.poll();
                order.offer(w);
                for (DirectedEdge v : g.adj(w)) {
                    degrees.indegree[v.to()]--;
                    if (degrees.indegree[v.to()] == 0) {
                        queue.offer(v.to());
                    }
                }
            }
        }

        public Iterable<Integer> order() {
            return order;
        }

    }

    public static class Degrees {
        public int[] indegree;
        public int[] outdegree;
        public EdgeWeightedGraph g;

        public Degrees(EdgeWeightedGraph g) {
            indegree = new int[g.V()];
            this.g = g;
            indegree = new int[g.V()];
            outdegree = new int[g.V()];
            for (int v = 0; v < g.V(); v++) {
                for (DirectedEdge w : g.adj(v)) {
                    indegree[w.to()]++;
                    outdegree[v]++;
                }
            }
        }

        public int indegree(int v) {
            return indegree[v];
        }

        public int outdegree(int v) {
            return outdegree[v];
        }

        public Iterable<Integer> sources() {
            Bag<Integer> bag = new Bag<>();
            for (int v = 0; v < g.V(); v++) {
                if (indegree[v] == 0) {
                    bag.add(v);
                }
            }
            return bag;
        }

        public Iterable<Integer> sinks() {
            Bag<Integer> bag = new Bag<>();
            for (int v = 0; v < g.V(); v++) {
                if (outdegree[v] == 0) {
                    bag.add(v);
                }
            }
            return bag;
        }

        public boolean isMap() {
            Bag<Integer> bag = new Bag<>();
            for (int i = 0; i < g.V(); i++) {
                if (outdegree[i] != 1) {
                    return false;
                }
            }
            return true;
        }
    }
}
